package com.zjsru.oneDay202210;

/**
 * @Author: likew
 * @Date: 2022/10/2
 * 在LR字符串中交换相邻字符
 *
 * 输入: start = "RXXLRXRXL", end = "XRLXXRRLX"
 * 输出: True
 * 解释:
 * 我们可以通过以下几步将start转换成end:
 * RXXLRXRXL ->
 * XRXLRXRXL ->
 * XRLXRXRXL ->
 * XRLXXRRXL ->
 * XRLXXRRLX
 *
 */
public class CanTransform {
    
    /**
     * 双指针
     * 两者操作可分别看做将 L 越过多个 X 向左移动，将 R 越过多个 X 向右移动。
     *
     * 序号相同的 L : start 的下标不小于 end 的下标（即 L 不能往右移动）
     * 序号相同的 R : start 的下标不大于 end 的下标（即 R 不能往左移动）
     *
     */
    public boolean canTransform(String start, String end) {
        int n = start.length(), i = 0, j = 0;
        while (j < n || i < n) {
            // 从start里面找到一个不是X的字符
            while (i < n && start.charAt(i) == 'X') {
                i++;
            }
            //从end里面找到一个不是X的字符
            while (j < n && end.charAt(j) == 'X') {
                j++;
            }
            // 如果有一个串遍历完成了，另一个串没有遍历完成 ，可以用i==j判断
            if (i == n || j == n) {
                return i == j;
            }
            //L与R无法交换，所以不相等肯定不能转换
            if (start.charAt(i) != end.charAt(j) ) {
                return false;
            }
            //L不能向右移动，所以start的L索引一定是大于end的L索引
            if (start.charAt(i) == 'L' && i < j) {
                return false;
            }
            //R不能向左移动，如果start的R索引在end对应的R索引右边，那肯定不能转换
            if (start.charAt(i) == 'R' && i > j) {
                return false;
            }
            //此时对应的字符可以移动
            i++;
            j++;
        }
        return i == j;
    }
    
    public static void main(String[] args) {
        CanTransform canTransform = new CanTransform();
        String start = "RXXLRXRXL";
        String end = "XRLXXRRLX";
        System.out.println(canTransform.canTransform(start, end));
    }
}
